package org.example.Soution002;

public class DoubleSearch {
    public static void main(String[] args) {
        DoubleSearch ds = new DoubleSearch();
        int[] nums=new int[] {1,3,5,6};
        System.out.println(ds.searchInsert(nums,4));
    }

    public int searchInsert(int[] nums, int target) {
        //头尾边界值
        if (target<nums[0]) {
            return 0;
        }
        if (target>nums[nums.length-1]) {
            return nums.length;
        }
        return doubleSearchInNums(nums,0,nums.length-1,target);
    }

    public int doubleSearchInNums(int[] nums, int head, int tail,int target) {
        if(tail<head) {
            return head;
        }
        int mid=(head+tail)/2;
        if(nums[mid]==target) {
            return mid;
        }else if(nums[mid]>target) {
            return doubleSearchInNums(nums,head,mid-1,target);
        }else{
            return doubleSearchInNums(nums,mid+1,tail,target);
        }

    }
}
